home *** CD-ROM | disk | FTP | other *** search
- /*
- * B G _ E V A L . C -- this file deals with evaulating the 'goodness'
- * of a backgammon situation by looking at the layouts and working
- * out various values based on characteristics of the layouts. The
- * weighted sum of these values is the 'goodness' of a particular
- * layout for a particular player.
- *
- * O.F.Ransen, 14th May 1994
- */
-
- #include <stdlib.h>
- #include <stdio.h>
- #include <string.h>
- #include <conio.h>
- #include "bg.h"
-
- /*************************************************************************/
-
- /***** Functions which look at particulars of the current situation *****/
- /***** All of these functions should return a number 0..100 *************/
- static long Runners_Score (Layout_t Me, Layout_t Him) ;
- static long Safety_Score (Layout_t Me, Layout_t Him) ;
- static long Tense_Aggro_Score (Layout_t Me, Layout_t Him) ;
- static long Wall_Score (Layout_t Me, Layout_t Him) ;
- static long Inner_Sec_Score (Layout_t Me, Layout_t Him) ;
- static long Outer_Sec_Score (Layout_t Me, Layout_t Him) ;
- static long Run_Sec_Score (Layout_t Me, Layout_t Him) ;
- static long Mid_Sec_Score (Layout_t Me, Layout_t Him) ;
- static long Agro_Coward_Score (Layout_t Me, Layout_t Him) ;
- static long Prime_Score (Layout_t Me, Layout_t Him);
- static long Entering_IT_Score (Layout_t Me) ;
- static long Exiting_Score (Layout_t Me, Layout_t Him) ;
- static short Get_Probs (Layout_t Me, Layout_t Him, short My_Pnt) ;
- static short Get_Hit_Prob (Layout_t Me, Layout_t Him, short My_Pnt, Dice_t* Dc) ;
- static long Constructor_Score (Layout_t Me, Layout_t Him) ;
-
- /*************************************************************************/
-
- static long Runners_Score (Layout_t Me, Layout_t Him)
- /*
- PURPOSE: To return a value based on my last piece.
- */
- {
- long p,Score ;
-
- p = 0 ;
- while ((Me[p] == 0) && (p < HOME_I)) {
- p++ ;
- }
-
- Score = (p*100)/(N_PLACES-1) ;
-
- return (Score) ;
- }
-
- /*************************************************************************/
-
- static long Safety_Score (Layout_t Me, Layout_t Him)
- /*
- PURPOSE: To return a value showing how 'safe' the situation is.
- NOTES: 1) If he has more than one piece on the bar and I have no uncovered
- pieces in my inner table then I am 100% safe.
- 2) If he has at least one piece on the bar and I have a 6 piece
- wall in my inner table then I am 100% safe.
- 3) If there is no overlap then I am 100% safe.
- */
- {
- #define TREMBLE 4 /* Start to get scared when prob >= (TREMBLE/36) */
- short p ;
- long Uncovered,Score ;
-
- if ((Him[BAR_I] > 1) && (Inner_Sec_Score(Me,Him) == 100l)) {
- Score = 100l ;
- } else if ((Him[BAR_I] > 0) && (Wall_Score (Me,Him) == 100l)) {
- Score = 100l ;
- } else if (!Overlap(Me,Him)) {
- Score = 100l ;
- } else {
- /* Rather more complicated... */
- Uncovered = 0 ;
- for (p = POINT1_I ; p <= POINT24_I ; p++) {
- if (Me[p] == 1) {
- if (Get_Probs (Me,Him,p) >= TREMBLE) {
- Uncovered++ ;
- }
- }
- }
- if (Uncovered > (long)MAX_MOVES) {
- Uncovered = (long)MAX_MOVES ;
- }
- Score= (long)((((long)MAX_MOVES-Uncovered)*100)/(long)MAX_MOVES) ;
- }
-
- return (Score) ;
- }
-
- /*************************************************************************/
- #if DRODBAR
- long Weighted_Safety (Layout_t Me, Layout_t Him)
- /*
- PURPOSE: To return a score based on the 'safeness' of the exposed
- pieces. We look at each single piece and calculate the probabilty
- that it will be hit by the next throw of the opponents dice. We
- add the probablilities up and return a number based on that.
- */
- {
- long Total = 0, Prob ;
- short p ;
-
- /* For every uncovered point... */
- for (p = 1 ; p < HOME_I ; p++) {
- if (Me[p] == 1) {
- Prob = (long)Get_Probs (Me,Him,p,TRUE) ;
- Total = Total + Prob ;
- }
- }
- return (Total) ;
- }
- #endif
- /*************************************************************************/
-
- static long Tense_Aggro_Score (Layout_t Me, Layout_t Him)
- /*
- PURPOSE: To balance the number of pieces I have eaten with the number
- of exposed pieces in his inner table. The score is high when
- I eat a lot and he has lots of exposed pieces.
- */
- {
- const long Max_Exposed = 6 ;
- const long Max_Eaten = 4 ;
-
- long Exposed, Eaten, Score ;
- short p;
-
- Exposed = 0 ;
- for (p = 19 ; p <= 24 ; p++) {
- if (Him[p] == 1) {
- Exposed++ ;
- }
- }
-
- Eaten = Him[BAR_I] ;
-
- Score = ((Exposed*100)/Max_Exposed) * ((Eaten*100)/Max_Eaten) ;
- return (Score/100) ;
- }
-
- /*************************************************************************/
-
- long Aggression_Score (Layout_t Me, Layout_t Him)
- /*
- PURPOSE: To return a value showing how many pieces have been eaten by me.
- NOTES: 1) Used in this file, but also in BG_FACE.C to draw the teeth!
- */
- {
- long Eaten ;
-
- Eaten = Him[BAR_I] ;
- if (Eaten > (long)MAX_MOVES) { /* Rare, so limit it's importance */
- Eaten = (long)MAX_MOVES ;
- }
- return ((Eaten*100l)/(long)MAX_MOVES) ;
- }
-
- /*************************************************************************/
-
- static long Wall_Score (Layout_t Me, Layout_t Him)
- /*
- PURPOSE: To return a score based on how much of a wall I have built in
- */
- {
- const short Max_Wall_Score = 6 ;
- long Score ;
- short p ;
-
- Score = 0 ;
- for (p = 19 ; p <= POINT24_I ; p++) {
- if (Me[p] > 1) {
- Score++ ;
- }
- }
- return ((Score*100)/Max_Wall_Score) ;
- }
-
- /*************************************************************************/
-
- static long Inner_Sec_Score (Layout_t Me, Layout_t Him)
- /*
- PURPOSE: To return a score based on how few of my pieces are
- uncovered in my inner table.
- */
- {
- long const Max_Uncovered = 6 ;
- long Uncovered ;
- short p ;
-
- Uncovered = 0 ;
- for (p = 19 ; p <= 24 ; p++) {
- if (Me[p] == 1) {
- Uncovered++ ;
- }
- }
- return (((Max_Uncovered-Uncovered)*100)/Max_Uncovered) ;
- }
-
- /*************************************************************************/
-
- static long Outer_Sec_Score (Layout_t Me, Layout_t Him)
- /*
- PURPOSE: To return a score based on how few pieces are uncovered
- in my outer table.
- */
- {
- long const Max_Uncovered = 6 ;
- long Uncovered ;
- short p ;
-
- Uncovered = 0 ;
- for (p = 13 ; p <= 18 ; p++) {
- if (Me[p] == 1) {
- Uncovered++ ;
- }
- }
- return (((Max_Uncovered-Uncovered)*100)/Max_Uncovered) ;
- }
-
- /*************************************************************************/
-
- static long Run_Sec_Score (Layout_t Me, Layout_t Him)
- /*
- PURPOSE: To return a score based on how few of my pieces are uncovered
- in his inner table.
- */
- {
- long const Max_Uncovered = 6 ;
- long Uncovered ;
- short p ;
-
- Uncovered = 0 ;
- for (p = 1 ; p <= 6 ; p++) {
- if (Me[p] == 1) {
- Uncovered++ ;
- }
- }
- return (((Max_Uncovered-Uncovered)*100)/Max_Uncovered) ;
- }
-
- /*************************************************************************/
-
- static long Mid_Sec_Score (Layout_t Me, Layout_t Him)
- /*
- PURPOSE: To return a score based on how few of my pieces are uncovered
- in his outer table.
- */
- {
- long const Max_Uncovered = 6 ;
- long Uncovered ;
- short p ;
-
- Uncovered = 0 ;
- for (p = 7 ; p <= 12 ; p++) {
- if (Me[p] == 1) {
- Uncovered++ ;
- }
- }
- return (((Max_Uncovered-Uncovered)*100)/Max_Uncovered) ;
- }
-
- /*************************************************************************/
-
- static long Agro_Coward_Score (Layout_t Me, Layout_t Him)
- /*
- PURPOSE: To return a score based on how many I can eat without risk.
- */
- {
- short p ;
- for (p = 19 ; p <= POINT24_I ; p++) {
- if (Me[p] == 1) {
- return (0) ;
- }
- }
- /* No uncovered pieces in home area, I can eat */
- return (Aggression_Score(Me,Him)) ;
- }
-
- /*************************************************************************/
-
- static long Prime_Score (Layout_t Me, Layout_t Him)
- /*
- PURPOSE: To return a score based on the longest run of occupied points
- */
- {
- #define MAX_PRIME 6
- long P_Count,Max_Found ;
- short p ;
-
- if (!Overlap (Me,Him)) {
- return (0l) ;
- }
-
- P_Count = 0 ;
- Max_Found = 0 ;
- for (p = 15 ; p < 22 ; p++) {
- if (Me[p] > 1) {
- P_Count++ ;
- if (P_Count > Max_Found) {
- Max_Found = P_Count ;
- }
- } else {
- P_Count=0 ;
- }
- }
- if (Max_Found >= MAX_PRIME) {
- return (100l) ;
- } else {
- return ((Max_Found*100l)/MAX_PRIME) ;
- }
- }
-
- /*************************************************************************/
-
- #define MAX_ENTERING_SCORE 49 /* These two defines force exiting... */
- #define MIN_EXITING_SCORE 51 /* ...to always win over entering... */
-
- static long Entering_IT_Score (Layout_t Me)
- /*
- PURPOSE: To return a value based on getting into my inner table.
- NOTES: 1) This is rather hand-crafted...
- */
- {
- #define FIRST_IT_POINT 19 /* Just inside the bar */
- #define MAX_END_PIECES 1
-
- long p,Score,N_End_Pieces ;
-
- p = BAR_I ;
- while ((Me[p] == 0) && (p < FIRST_IT_POINT)) {
- p++ ;
- }
-
- if (p >= FIRST_IT_POINT) {
- Error_Exit ("Entering score when bearing off!") ;
- }
-
- N_End_Pieces = Me[p] ;
- if (N_End_Pieces > 1) {
- /*
- * There is a column to be shifted, return a very low score
- */
- if (N_End_Pieces > MAX_END_PIECES) {
- N_End_Pieces = MAX_END_PIECES ;
- }
- Score = MAX_END_PIECES - N_End_Pieces ;
- } else {
- /*
- * There is just a single trailing piece
- */
- Score = (p*MAX_ENTERING_SCORE)/(FIRST_IT_POINT-1) ;
- }
-
- return (Score) ;
- }
-
- /*************************************************************************/
-
- static long Exiting_Score (Layout_t Me, Layout_t Him)
- /*
- PURPOSE: To return a number based how many pieces I have taken off
- the board or how close I have got to taking them off
- */
- {
- long Score ;
- Score = (Me[HOME_I]*(100l-MIN_EXITING_SCORE))/(long)N_PIECES ;
- Score = Score + MIN_EXITING_SCORE ;
- return (Score);
- }
-
- /*************************************************************************/
-
- static short Get_Probs (Layout_t Me, Layout_t Him, short My_Point)
- /*
- PURPOSE: To return a number (0..36 inclusive) which gives the
- probability that the point will be hit by the opponent.
- */
- {
- Dice_t Dice ;
- short Total,d0,d1,i,Loc_Tot ;
-
- Total = 0 ;
-
- for (d0 = 1 ; d0 <= 6 ; d0++) {
- for (d1 = 1 ; d1 <= 6 ; d1++) {
- if (d1 == d0) {
- Dice.N_Vals = 4 ;
- for (i = 0 ; i < 4 ; i++) {
- Dice.Values[i] = (char)d0 ;
- }
- } else {
- Dice.N_Vals = 2 ;
- Dice.Values[0] = (char)d0 ;
- Dice.Values[1] = (char)d1 ;
- }
- Loc_Tot = Get_Hit_Prob (Me,Him,My_Point,&Dice) ;
- Total = Total + Loc_Tot ;
- }
- }
-
- return (Total) ;
- }
-
- /*************************************************************************/
-
- static short Get_Hit_Prob (Layout_t Me, Layout_t Him, short My_Point, Dice_t* Dice)
- /*
- PURPOSE: To return 0 if the piece cannot be hit with the Dice, or
- 1 if it can be hit.
- */
- {
- short His_Point,His_Start,Mine,i,d0,d1 ;
- short Long_Point,Mediate_Point0,Mediate_Point1 ;
-
- if (Me[My_Point] != 1) {
- return (0) ;
- }
-
- His_Point = Reverse_Index (My_Point) ;
- d0 = Dice->Values[0] ;
- d1 = Dice->Values[1] ;
-
- if (Dice->N_Vals == 4) {
- /* Hit via double */
- for (i = 1 ; i <= 4 ; i++) {
- His_Start = His_Point - (d0*i) ; /* Where he starts from */
- Mine = Reverse_Index (His_Start) ;
- if (His_Start < BAR_I) {
- return (0) ; /* He can't be at less than the bar point */
- } else if (Me[Mine] > 1) {
- return (0) ; /* I occupy that point */
- } else if (Him[His_Start] > 0) {
- return (1) ; /* He could get me with that piece */
- }
- }
- return (0) ;
- } else {
- /* Check for direct hit with first dice... */
- His_Start = His_Point - d0 ;
- if (His_Start >= BAR_I) {
- if (Him[His_Start] > 0) {
- return (1) ;
- }
- }
-
- /* Check for direct hit with second dice... */
- His_Start = His_Point - d1 ;
- if (His_Start >= BAR_I) {
- if (Him[His_Point-d1] > 0) {
- return (1) ;
- }
- }
-
- /* Check for an indirect hit... */
- Long_Point = His_Point - (d0 + d1) ;
- if (Long_Point < BAR_I) {
- return (0) ;
- } else if (Him[Long_Point] == 0) {
- return (0) ;
- } else {
- Mediate_Point0 = Reverse_Index (His_Point - d0) ;
- Mediate_Point1 = Reverse_Index (His_Point - d1) ;
- if ((Me[Mediate_Point0] > 1) && (Me[Mediate_Point1] > 1)) {
- return (0) ; /* I block indirect hit */
- } else {
- return (1) ; /* No blockage */
- }
- }
- }
- }
-
- /*************************************************************************/
-
- boolean Overlap (Layout_t Me, Layout_t Him)
- /*
- PURPOSE: To return TRUE if there are any of his pieces in front of any
- of mine.
- */
- {
- short p, My_Last ;
-
- My_Last = HOME_I ; /* Optimistic */
- for (p = HOME_I ; p >= BAR_I ; p--) {
- if (Me[p] != 0) {
- My_Last = p ;
- }
- }
-
- p = Reverse_Index (My_Last) ;
- while (p >= BAR_I) {
- if (Him[p] != 0) {
- return (TRUE) ;
- }
- p-- ;
- }
-
- return (FALSE) ;
- }
-
- /***************************************************************************/
-
- short Pip_Count (Layout_t Layout)
- /*
- PURPOSE: To return the pip count of this layout
- NOTES: Smaller numbers are better, means less pieces far away.
- */
- {
- short p,P_Count ;
-
- P_Count = 0 ;
- for (p = BAR_I ; p <= HOME_I ; p++) {
- P_Count = P_Count + ((HOME_I-p)*Layout[p]) ;
- }
-
- if (P_Count < 0) {
- Error_Exit ("P_Count < 0") ;
- }
-
- return (P_Count) ;
- }
-
- /*************************************************************************/
-
- short Pip_Count_Diff (Layout_t Me, Layout_t Him)
- /*
- PURPOSE: To return a number showing the 'advantage' one player has over
- the other. If the number is negative He has the advantage, if
- the number is positive I have the advantage.
- */
- {
- short Mine,His ;
-
- Mine = Pip_Count (Me) ;
- His = Pip_Count (Him) ;
-
- return (His - Mine) ;
- }
-
- /*************************************************************************/
-
- long Pip_Count_Score (Layout_t Me, Layout_t Him)
- /*
- PURPOSE: To return a score based on the pip count.
- */
- {
- const long Worst_Pips = -375l ;
- const long Pips_Range = (375l*2l) ;
- long Pips,Score ;
-
- Pips = (long)Pip_Count_Diff (Me,Him) ;
- Score = ((Pips - Worst_Pips)*100l)/Pips_Range ;
-
- return (Score) ;
- }
-
- /*************************************************************************/
-
- short Total_Pieces_On_Board (Layout_t Me, Layout_t Him)
- /*
- PURPOSE: To return the number of pieces left on the board.
- */
- {
- short Mine,His ;
-
- Mine = Pieces_On_Board (Me) ;
- His = Pieces_On_Board (Him) ;
-
- return (Mine + His) ;
- }
-
- /*************************************************************************/
-
- short Pieces_On_Board (Layout_t Layout)
- /*
- PURPOSE: To return the number of pieces left on the board in My layout
- */
- {
- short Pieces ;
-
- Pieces = 15 - Layout[HOME_I] ;
-
- return (Pieces) ;
- }
-
- /*************************************************************************/
-
- static long Constructor_Score (Layout_t Me, Layout_t Him)
- /*
- PURPOSE: To return a score based on the number of constructors in
- my outer table.
- */
- {
- #define QUARTER 9 /* 9/36 = a quarter no? */
- long Count,Danger ;
- short p ;
-
- /*
- * See if we have the basis for construction...
- */
- if (Me[19] < 3) {
- return (0l) ;
- }
- if (!((Me[18] > 2) || (Me[17] > 2))) {
- return (0l) ;
- }
-
- /*
- * If we get here we have a fullish bar point and a fattish
- * pre-bar point too. Now see how many single constructors
- * there are...
- */
- Count = 0 ;
- Danger = 0 ;
- for (p = 14 ; p <= 16 ; p++) {
- if (Me[p] == 1) {
- Danger = Danger + Get_Probs (Me,Him,p) ;
- Count++ ;
- }
- }
- if (Count > 0) {
- if ((Danger/Count) > QUARTER) {
- Count = 0 ;
- }
- }
-
- return ((Count*100l)/3l) ;
- }
-
- /*************************************************************************/
-
- /* The W_Func_t, holds the function, the name of the function (in
- many languages), and the weight for the function for both players. */
-
- typedef struct {
- long (*W_Func)(Layout_t,Layout_t) ; /* Type of function */
- long Weight [N_PLAYERS] ; /* Weights for each player */
- long Min,Max ; /* For later analysis */
- char Name [32] ; /* For later analysis */
- } W_Func_t ;
-
- static W_Func_t W_F_Table [N_WEIGHTS] = {
- /* Function, weight min max id */
- {Runners_Score, {0,0}, 200,-200,"Runners " },
- {Prime_Score, {0,0}, 200,-200,"Prime " },
- {Safety_Score, {0,0}, 200,-200,"Safety " },
- {Aggression_Score, {0,0}, 200,-200,"Aggro " },
- {Tense_Aggro_Score, {0,0}, 200,-200,"Tense Aggro " },
- {Wall_Score, {0,0}, 200,-200,"Wall " },
- {Agro_Coward_Score, {0,0}, 200,-200,"Agro Coward " },
- {Inner_Sec_Score, {0,0}, 200,-200,"Inr Sec " },
- {Outer_Sec_Score, {0,0}, 200,-200,"Outr Sec " },
- {Run_Sec_Score, {0,0}, 200,-200,"Run Sec " },
- {Mid_Sec_Score, {0,0}, 200,-200,"Mid Sec " },
- {Pip_Count_Score, {0,0}, 200,-200,"Pip Score " },
- {Constructor_Score, {0,0}, 200,-200,"Constructor " }
- } ;
-
- /*************************************************************************/
- /* See BG_USER1.C and BG.H for names of opponents */
- long Weights [N_OPPS][N_WEIGHTS] = {
- /*runrs pri safe aggro tenagr wall agrwal innr outr runsec midsec pips cons */
- { 73, 0, 23, 50, 79, 35, 50, 100, 25, 60, 75, 75, 16}, // Sergio
- { 36, 50, 24, 76, 48, 20, 44, 46, 50, 40, 5, 64, 58}, // Enzo
- { 58, 10, 38, 85, 54, 70, 45, 70, 70, 35, 70, 60, 0}, // Owen
- { 51, 65, 59, 51, 10, 25, 10, 51, 90, 35, 15, 69, 10}, // Brian
- } ;
-
- static short Curr_Opponent = SERGIO ;
-
- void Setup_Weights (short New_Opponent, Player_t Player)
- /*
- PURPOSE: To copy the opponents weights into the W_F_Table.
- The Player will be black or white, and we must copy
- the opponents weights into the black or white list
- of weights. The list of weights of the human (white or
- black) are set to 0 to speed up evaluation.
- */
- {
- short w ;
- for (w = 0 ; w < N_WEIGHTS ; w++) {
- W_F_Table[w].Weight[Player] = Weights[New_Opponent][w] ;
- W_F_Table[w].Weight[OPPONENT(Player)] = 0 ;
- }
- if (Curr_Opponent != New_Opponent) {
- Init_Stats () ;
- Curr_Opponent = New_Opponent ;
- }
- }
-
- /*************************************************************************/
-
- static short Curr_Black_Id = SERGIO ;
- static short Curr_White_Id = ENZO ;
-
- void Init_Genetic_Opponents (short Black, short White)
- /*
- PURPOSE: To set the black players weights to the values in
- Weights[BLACK], and the white players weights to the values in
- Weights[WHITE].
- */
- {
- short w ;
- for (w = 0 ; w < N_WEIGHTS ; w++) {
- W_F_Table[w].Weight[BLACK_PLAYER] = Weights[Black][w] ;
- W_F_Table[w].Weight[WHITE_PLAYER] = Weights[White][w] ;
- }
- Curr_Black_Id = Black ;
- Curr_White_Id = White ;
- }
-
- /*************************************************************************/
-
- long Evaluate_Move (Layout_t Me, Layout_t Him, Player_t Player)
- /*
- PURPOSE: To return the weighted sum for this player and his situation.
- */
- {
- long Score,Temp ;
- extern boolean Debugging,Genetics ;
- ushort w ;
-
- if (!Overlap(Me,Him)) {
- /* The choice of move is rather simple, we are just racing */
- if (!Bearing_Off(Me)) {
- Score = Entering_IT_Score (Me) ; /* Move closer to inner table */
- } else {
- Score = Exiting_Score (Me,Him) ; /* Take pieces off inner table */
- }
- return (Score) ;
- }
-
- // Using normal statistics methods, not the NN brain
- Score = 0 ;
- for (w = 0 ; w < N_WEIGHTS ; w++) {
- /* Get the value for this weight */
- Temp = (*W_F_Table[w].W_Func) (Me,Him) ;
- /* Check the value is not illegal */
- if (Temp < 0) {
- printf ("\nAn evaluation score = %ld, w=%d, <%s>.",Temp,w,W_F_Table[w].Name) ;
- Error_Exit ("A negative evaluation score") ;
- } else if (Temp > 100) {
- printf ("\nAn evaluation score = %ld, w=%d,<%s>.",Temp,w,W_F_Table[w].Name) ;
- Error_Exit ("An evaluation greater than 100") ;
- }
- /* Record the excursions of the weight for later analysis */
- if (Temp > W_F_Table[w].Max) {
- W_F_Table[w].Max = Temp ;
- }
- if (Temp < W_F_Table[w].Min) {
- W_F_Table[w].Min = Temp ;
- }
- /* Add the value into the score */
- Score = Score + (W_F_Table[w].Weight[Player]*Temp) ;
- }
-
- return (Score) ;
- }
-
- /*************************************************************************/
-
-